package leetcode.array;

import java.util.*;
import java.util.stream.Collectors;

/**
 * leetCode 16
 *  4Sum
 * 四数之和
 * 翻译：和等于定值的四数的集合
 * 思路：2SUM建Map，key为每两个数的和，值为List<int [2]>，存两数的索引，再按2Sum遍历Map

 */
public class Array18 {

    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        List<Integer> input = Arrays.stream(str.split(",")).map(i -> { return Integer.parseInt(i); }).collect(Collectors.toList());
        System.out.println(Arrays.toString(input.toArray()));
        Integer [] nums = input.toArray(new Integer[input.size()]);
        int target = Integer.parseInt(sc.next());
        new Array18().fourSum(nums, target);
    }
    public List<List<Integer>> fourSum(Integer[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 4) {
            return res;
        }

        Arrays.sort(nums);

        HashMap<Integer, List<Integer[]>> map = new HashMap<>();
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int sum = nums[i] + nums[j];
                Integer[] pair = {i, j};

                if (!map.containsKey(sum)) {
                    map.put(sum, new ArrayList<Integer[]>());
                }
                map.get(sum).add(pair);
            }
        }

        Set<Integer> keys = map.keySet();
        for (int key : keys) {
            List<Integer[]> listA = map.get(key);
            List<Integer[]> listB = map.get(target - key);

            if (listA != null && listB != null) {
                for (Integer[] pairA : listA) {
                    int a0 = pairA[0], a1 = pairA[1];

                    for (Integer[] pairB : listB) {
                        int b0 = pairB[0], b1 = pairB[1];
                        if (a1 < b0) {  // 因为肯定存在： a0 < a1, b0 < b1
                            List<Integer> list = new ArrayList<>();
                            list.add(nums[a0]);
                            list.add(nums[a1]);
                            list.add(nums[b0]);
                            list.add(nums[b1]);
                            if (!res.contains(list)) res.add(list);
                        }
                    }
                }
            }
        }

        return res;
    }
}
